<html>
 <head>
  <meta charset="UTF-8">
 </head>
 <body>
  <h1 data-lake-id="wqaMY" id="wqaMY"><span data-lake-id="ua1a53749" id="ua1a53749">典型回答</span></h1>
  <p data-lake-id="u77bb1318" id="u77bb1318"><br></p>
  <p data-lake-id="uab2c03bb" id="uab2c03bb"><span data-lake-id="u3d978222" id="u3d978222">常见的5种方法：</span></p>
  <ol list="u543fd2b7">
   <li fid="uf880712e" data-lake-id="u8a45035e" id="u8a45035e"><span data-lake-id="ucc0bf244" id="ucc0bf244">开放定址法</span></li>
  </ol>
  <ul list="u8b175840" data-lake-indent="1">
   <li fid="uae823142" data-lake-id="u40b72650" id="u40b72650"><span data-lake-id="u60497e2e" id="u60497e2e">开放定址法就是一旦发生了冲突，就去寻找下一个空的散列地址，只要散列表足够大，空的散列地址总能找到，并将记录存入。</span></li>
   <li fid="uae823142" data-lake-id="u40cf9a67" id="u40cf9a67"><span data-lake-id="u5b66ec9e" id="u5b66ec9e">常见的开放寻址技术有线性探测、二次探测和双重散列。</span></li>
   <li fid="uae823142" data-lake-id="ud8eee8dd" id="ud8eee8dd"><span data-lake-id="u4a4582f7" id="u4a4582f7">这种方法的缺点是可能导致“聚集”问题，降低哈希表的性能。</span></li>
  </ul>
  <ol list="u6451c1f9" start="2">
   <li fid="u4199d27f" data-lake-id="uc44d22dd" id="uc44d22dd"><span data-lake-id="uace5e197" id="uace5e197">链地址法</span></li>
  </ol>
  <ul list="u8b175840" start="4" data-lake-indent="1">
   <li fid="uae823142" data-lake-id="ub0147064" id="ub0147064"><span data-lake-id="u9ed9f9ea" id="u9ed9f9ea">最常用的解决哈希冲突的方法之一。</span></li>
   <li fid="uae823142" data-lake-id="u17e7ef00" id="u17e7ef00"><span data-lake-id="u83eebfb9" id="u83eebfb9">每个哈希桶（bucket）指向一个链表。当发生冲突时，新的元素将被添加到这个链表的末尾。</span></li>
   <li fid="uae823142" data-lake-id="u80c69d7f" id="u80c69d7f"><span data-lake-id="uac6ce5a2" id="uac6ce5a2">在Java中，HashMap就是通过这种方式来解决哈希冲突的。Java 8之前，HashMap使用链表来实现；从Java 8开始，当链表长度超过一定阈值时，链表会转换为红黑树，以提高搜索效率。</span></li>
  </ul>
  <ol list="u14f1b980" start="3">
   <li fid="u59278df1" data-lake-id="ub753ddbb" id="ub753ddbb"><span data-lake-id="u4fb893d0" id="u4fb893d0">再哈希法</span></li>
  </ol>
  <ul list="u8b175840" start="7" data-lake-indent="1">
   <li fid="uae823142" data-lake-id="uc9ec9416" id="uc9ec9416"><span data-lake-id="u01db74fe" id="u01db74fe">当哈希地址发生冲突用其他的函数计算另一个哈希函数地址，直到冲突不再产生为止。</span></li>
   <li fid="uae823142" data-lake-id="u7cfa1fe0" id="u7cfa1fe0"><span data-lake-id="u0ef62fcb" id="u0ef62fcb">这种方法需要额外的计算，但可以有效降低冲突率。</span></li>
  </ul>
  <ol list="uc02d36c2" start="4">
   <li fid="uce9c682b" data-lake-id="u35b7b8e3" id="u35b7b8e3"><span data-lake-id="u48bbf825" id="u48bbf825">建立公共溢出区</span></li>
  </ol>
  <ul list="u8ce01c28" data-lake-indent="1">
   <li fid="uae823142" data-lake-id="u7ab88595" id="u7ab88595"><span data-lake-id="u9cb3fd8e" id="u9cb3fd8e">将哈希表分为基本表和溢出表两部分，发生冲突的元素都放入溢出表中。</span></li>
  </ul>
  <ol list="uc02d36c2" start="5">
   <li fid="uce9c682b" data-lake-id="ufac3bd95" id="ufac3bd95"><span data-lake-id="ue63b40e8" id="ue63b40e8">一致性hash</span></li>
  </ol>
  <ul list="u8b175840" start="9" data-lake-indent="1">
   <li fid="uae823142" data-lake-id="u11706915" id="u11706915"><span data-lake-id="u25ff4b68" id="u25ff4b68">主要用于分布式系统中，如分布式缓存。它通过将数据均匀分布到多个节点上来减少冲突。</span></li>
  </ul>
  <p data-lake-id="u7885f66b" id="u7885f66b"><span data-lake-id="u48124b1e" id="u48124b1e">​</span><br></p>
  <p data-lake-id="ud384ac0c" id="ud384ac0c"><span data-lake-id="uc865fb38" id="uc865fb38">​</span><br></p>
  <h1 data-lake-id="FikFX" id="FikFX"><span data-lake-id="u4be90c9b" id="u4be90c9b">扩展知识</span></h1>
  <h2 data-lake-id="NhYU6" id="NhYU6"><span data-lake-id="udeca1c68" id="udeca1c68">链地址法</span></h2>
  <p data-lake-id="u8176e4ff" id="u8176e4ff"><span data-lake-id="u52c9caf3" id="u52c9caf3">HashMap采用该方法，当出现hash冲突的时候，会使同一个hash的所有值形成一个链表。查询的时候，首先通过hash定位到该链表，然后再遍历链表获得结果。</span></p>
  <p data-lake-id="u14a60842" id="u14a60842"><span data-lake-id="uc18e6cb9" id="uc18e6cb9">​</span><br></p>
  <p data-lake-id="u3402666c" id="u3402666c"><img src="https://cdn.nlark.com/yuque/0/2023/png/5378072/1692799464985-6ab71813-5adf-4a17-b273-b6db8c4040e8.png?x-oss-process=image%2Fwatermark%2Ctype_d3F5LW1pY3JvaGVp%2Csize_25%2Ctext_SmF2YeWFq-iCoV9CeSBIb2xsaXM%3D%2Ccolor_FFFFFF%2Cshadow_50%2Ct_80%2Cg_se%2Cx_10%2Cy_10%2Fwatermark%2Ctype_d3F5LW1pY3JvaGVp%2Csize_25%2Ctext_SmF2YSA4IEd1IFA%3D%2Ccolor_FFFFFF%2Cshadow_50%2Ct_80%2Cg_se%2Cx_10%2Cy_10"></p>
  <p data-lake-id="u39c2b272" id="u39c2b272"><br></p>
  <p data-lake-id="u8d97a220" id="u8d97a220"><span data-lake-id="u6c2faecd" id="u6c2faecd">此时，对于hash(5)和hash(6)的冲突来说，则会在hash表的第三个节点形成链表，如：hash[3]-&gt;5-&gt;6</span></p>
  <p data-lake-id="u275057c4" id="u275057c4"><span data-lake-id="u2a40958f" id="u2a40958f">​</span><br></p>
  <p data-lake-id="uecc40ee5" id="uecc40ee5"><span data-lake-id="u446833e9" id="u446833e9">优点：</span></p>
  <ol list="ubbfccd14">
   <li fid="u3bcc4c45" data-lake-id="ub063c8fa" id="ub063c8fa"><span data-lake-id="u26c715d1" id="u26c715d1">处理冲突简单</span></li>
   <li fid="u3bcc4c45" data-lake-id="u41d31848" id="u41d31848"><span data-lake-id="uf3610f6f" id="uf3610f6f">适合经常插入和删除的情况下</span></li>
   <li fid="u3bcc4c45" data-lake-id="u0536eed2" id="u0536eed2"><span data-lake-id="u81cf691c" id="u81cf691c">适合没有预定空间的情况</span></li>
  </ol>
  <p data-lake-id="u4ecdd0b3" id="u4ecdd0b3"><span data-lake-id="uc379cd3f" id="uc379cd3f">缺点</span></p>
  <ol list="u3ebeaff0">
   <li fid="u498f56f4" data-lake-id="ua292d323" id="ua292d323"><span data-lake-id="u13d7445d" id="u13d7445d">当冲突较多的时候，查询复杂度趋近于O(n)</span></li>
  </ol>
  <h2 data-lake-id="i3siS" id="i3siS"><span data-lake-id="udf56a2ee" id="udf56a2ee">开放定址法</span></h2>
  <p data-lake-id="u1e683d35" id="u1e683d35"><span data-lake-id="u72ef0efa" id="u72ef0efa">开放定址法是解决哈希表中哈希冲突的一种方法。与链地址法不同，开放寻址法在哈希表本身的数组中寻找空闲位置来存储冲突的元素。这种方法的关键在于，当一个新的键通过哈希函数定位到一个已被占用的槽位时，它将探索哈希表的其他槽位，直到找到一个空槽位</span><span data-lake-id="u51e0e43e" id="u51e0e43e" class="lake-fontsize-12" style="color: rgb(55, 65, 81)">。</span></p>
  <p data-lake-id="ub1e92d25" id="ub1e92d25"><span data-lake-id="u63a6a282" id="u63a6a282" class="lake-fontsize-12" style="color: rgb(55, 65, 81)">​</span><br></p>
  <p data-lake-id="uc28a5d6c" id="uc28a5d6c"><span data-lake-id="u70ebfc16" id="u70ebfc16">开放寻址法主要有以下几种实现方式：</span></p>
  <ol list="u8e6794fb">
   <li fid="uafe711a1" data-lake-id="u784974c6" id="u784974c6"><strong><span data-lake-id="u1bab4199" id="u1bab4199">线性探测（Linear Probing）</span></strong><span data-lake-id="u6b6a4f0c" id="u6b6a4f0c">：</span></li>
  </ol>
  <ul list="u81f73f26" data-lake-indent="1">
   <li fid="u36ed234a" data-lake-id="u1feb5783" id="u1feb5783"><span data-lake-id="u30ae0c16" id="u30ae0c16">当发生冲突时，顺序检查表中的下一个槽位。</span></li>
   <li fid="u36ed234a" data-lake-id="u55c3d924" id="u55c3d924"><span data-lake-id="uf71b9899" id="uf71b9899">如果该槽位也被占用，则继续向下检查，直到找到一个空槽位。</span></li>
   <li fid="u36ed234a" data-lake-id="u4b8cd572" id="u4b8cd572"><u><span data-lake-id="ua547b14a" id="ua547b14a">线性探测的问题在于“聚集”：一旦发生多次连续冲突，就会形成一长串被占用的槽位，这会影响后续插入和查找的效率。</span></u></li>
  </ul>
  <p data-lake-id="u58d567bf" id="u58d567bf"><br></p>
  <p data-lake-id="u4a12d4cd" id="u4a12d4cd"><span data-lake-id="u5591fad1" id="u5591fad1">如使用大小为7的hash表，依次存储5、8、15、1</span></p>
  <p data-lake-id="ue45c2f75" id="ue45c2f75"><img src="https://cdn.nlark.com/yuque/0/2024/png/5378072/1705730324068-75f7955c-06d1-4532-ad56-789a1d2c904f.png?x-oss-process=image%2Fwatermark%2Ctype_d3F5LW1pY3JvaGVp%2Csize_54%2Ctext_SmF2YSA4IEd1IFA%3D%2Ccolor_FFFFFF%2Cshadow_50%2Ct_80%2Cg_se%2Cx_10%2Cy_10"></p>
  <p data-lake-id="u06c4703b" id="u06c4703b"><br></p>
  <ol list="u8e6794fb" start="2">
   <li fid="uafe711a1" data-lake-id="ua7410ff7" id="ua7410ff7"><strong><span data-lake-id="u4baf9f08" id="u4baf9f08">二次探测（Quadratic Probing）</span></strong><span data-lake-id="u16a77e28" id="u16a77e28">：</span></li>
  </ol>
  <ul list="ubcc8e8a1" data-lake-indent="1">
   <li fid="ud96eca32" data-lake-id="u4d89e037" id="u4d89e037"><span data-lake-id="uf48f772c" id="uf48f772c">使用二次方的序列来探测下一个槽位（例如，1, 4, 9, 16, ...）。</span></li>
   <li fid="ud96eca32" data-lake-id="u8181f59e" id="u8181f59e"><span data-lake-id="u0e4eacaa" id="u0e4eacaa">这种方法可以减少聚集的问题，但仍然可能存在较小范围的聚集。</span></li>
  </ul>
  <p data-lake-id="u305e6a1b" id="u305e6a1b"><span data-lake-id="uea951d97" id="uea951d97">​</span><br></p>
  <p data-lake-id="u6ca492b8" id="u6ca492b8"><span data-lake-id="u9374177c" id="u9374177c">同样是依次存储5、8、15、1，当存储到15和1的时候开始冲突，结果如下：</span></p>
  <p data-lake-id="u742b1763" id="u742b1763"><img src="https://cdn.nlark.com/yuque/0/2024/png/5378072/1705730862460-c15e1d88-46cb-440d-8620-f6f33d6bedf0.png?x-oss-process=image%2Fwatermark%2Ctype_d3F5LW1pY3JvaGVp%2Csize_55%2Ctext_SmF2YSA4IEd1IFA%3D%2Ccolor_FFFFFF%2Cshadow_50%2Ct_80%2Cg_se%2Cx_10%2Cy_10"></p>
  <p data-lake-id="u09555404" id="u09555404"><span data-lake-id="u397d3595" id="u397d3595">​</span><br></p>
  <ol list="u8e6794fb" start="3">
   <li fid="uafe711a1" data-lake-id="ua34d388b" id="ua34d388b"><strong><span data-lake-id="u12c49849" id="u12c49849">双重散列（Double Hashing）</span></strong><span data-lake-id="u3e3044f5" id="u3e3044f5">：</span></li>
  </ol>
  <ul list="uf2020907" data-lake-indent="1">
   <li fid="uc90f886b" data-lake-id="u38bd2772" id="u38bd2772"><span data-lake-id="u1eb12461" id="u1eb12461">使用两个不同的哈希函数。</span></li>
   <li fid="uc90f886b" data-lake-id="u14cbfbf1" id="u14cbfbf1"><span data-lake-id="uecaa99d1" id="uecaa99d1">当第一个哈希函数导致冲突时，使用第二个哈希函数来确定探测序列。</span></li>
   <li fid="uc90f886b" data-lake-id="u0d2482ab" id="u0d2482ab"><span data-lake-id="u81d45793" id="u81d45793">这种方法的优点是减少了聚集，并且能更好地分散键的分布。</span></li>
   <li fid="uc90f886b" data-lake-id="ua029ac11" id="ua029ac11"><span data-lake-id="ub356570e" id="ub356570e">​</span><br></li>
  </ul>
  <p data-lake-id="uf1fed38a" id="uf1fed38a"><span data-lake-id="u5611c631" id="u5611c631">同样是依次存储5、8、15、1，假设第二个哈希函数为 </span><code data-lake-id="u50187eea" id="u50187eea"><span data-lake-id="u6d258bc2" id="u6d258bc2">hash2(key) = 3 - (key % 3)</span></code><span data-lake-id="u0a7fe529" id="u0a7fe529">。</span></p>
  <p data-lake-id="u3c60570a" id="u3c60570a"><span data-lake-id="u64f5b79d" id="u64f5b79d">​</span><br></p>
  <p data-lake-id="u3494c30e" id="u3494c30e"><img src="https://cdn.nlark.com/yuque/0/2024/png/5378072/1705731117730-da027322-9e35-4413-aadb-fa5fecb27549.png?x-oss-process=image%2Fwatermark%2Ctype_d3F5LW1pY3JvaGVp%2Csize_38%2Ctext_SmF2YSA4IEd1IFA%3D%2Ccolor_FFFFFF%2Cshadow_50%2Ct_80%2Cg_se%2Cx_10%2Cy_10"></p>
  <ul list="uf2020907" start="5" data-lake-indent="1">
   <li fid="uc90f886b" data-lake-id="uf19cb2bc" id="uf19cb2bc"><span data-lake-id="u9c271b0a" id="u9c271b0a">​</span><br></li>
  </ul>
  <p data-lake-id="u1b1bdab9" id="u1b1bdab9"><span data-lake-id="uf76b77c2" id="uf76b77c2">开放定址法的</span><strong><span data-lake-id="u4906d1e9" id="u4906d1e9">优点是</span></strong><span data-lake-id="u6d513a09" id="u6d513a09">：</span></p>
  <ul list="u82ba61aa">
   <li fid="udfe8e81d" data-lake-id="uf5934e8a" id="uf5934e8a" data-lake-index-type="true"><span data-lake-id="ud576d077" id="ud576d077">空间效率</span><span data-lake-id="u42bb943a" id="u42bb943a">：由于不需要额外的数据结构（如链表），开放寻址法通常比链地址法使用更少的内存。</span></li>
   <li fid="udfe8e81d" data-lake-id="u4eb6f0bf" id="u4eb6f0bf" data-lake-index-type="true"><span data-lake-id="ua82cbb7e" id="ua82cbb7e">缓存友好性：由于数据存储在连续的内存空间，所以在寻址时可能有更好的缓存性能。</span></li>
  </ul>
  <p data-lake-id="ud4b8d3f5" id="ud4b8d3f5"><br></p>
  <p data-lake-id="u5f3874d1" id="u5f3874d1"><span data-lake-id="u452488bb" id="u452488bb">然而，开放寻址法也</span><strong><span data-lake-id="ub1a0050d" id="ub1a0050d">有缺点</span></strong><span data-lake-id="u1219abda" id="u1219abda">：</span></p>
  <p data-lake-id="ua3a23bf1" id="ua3a23bf1"><span data-lake-id="u8764394f" id="u8764394f">​</span><br></p>
  <ul list="ua309c22e">
   <li fid="u0696b52f" data-lake-id="u194a3a2a" id="u194a3a2a" data-lake-index-type="true"><span data-lake-id="u869e48d5" id="u869e48d5">当负载因子（即表中已占用的槽位比例）较高时，查找空槽位的时间可能会显著增加。</span></li>
   <li fid="u0696b52f" data-lake-id="u9695e9a9" id="u9695e9a9" data-lake-index-type="true"><span data-lake-id="u594e9524" id="u594e9524">删除操作相对复杂，因为简单地将槽位置为空可能会打断探测序列。</span></li>
  </ul>
  <p data-lake-id="ua48cbbc9" id="ua48cbbc9"><br></p>
  <h2 data-lake-id="rnTpV" id="rnTpV"><span data-lake-id="u47801aba" id="u47801aba">再哈希法</span></h2>
  <p data-lake-id="uc85f1648" id="uc85f1648"><span data-lake-id="uedf2bc18" id="uedf2bc18">当发生冲突时，需要更换hash函数，直到新的hash函数没有冲突</span></p>
  <p data-lake-id="u7a09d470" id="u7a09d470"><span data-lake-id="uc2c3a552" id="uc2c3a552">​</span><br></p>
  <p data-lake-id="uddf8780a" id="uddf8780a"><span data-lake-id="u3b3be3c0" id="u3b3be3c0">假设两个哈希函数定义如下：</span></p>
  <ul list="u2fa90e68">
   <li fid="uc834c604" data-lake-id="ue0ac0dfe" id="ue0ac0dfe" data-lake-index-type="true"><span data-lake-id="ua555ec32" id="ua555ec32">第一个哈希函数：</span><code data-lake-id="u0b647916" id="u0b647916"><span data-lake-id="u4786e69b" id="u4786e69b">hash1(key) = key % 7</span></code></li>
   <li fid="uc834c604" data-lake-id="u4d930169" id="u4d930169" data-lake-index-type="true"><span data-lake-id="u277b1fba" id="u277b1fba">第二个哈希函数：</span><code data-lake-id="ua1171ca4" id="ua1171ca4"><span data-lake-id="ud5a5ea09" id="ud5a5ea09">hash2(key) = key % 7 + key % 10</span></code></li>
  </ul>
  <p data-lake-id="ue9f7e8f7" id="ue9f7e8f7"><span data-lake-id="ue10a9ba4" id="ue10a9ba4">我们要插入的键值是：5、8、15、1</span></p>
  <p data-lake-id="uebe9a766" id="uebe9a766"><img src="https://cdn.nlark.com/yuque/0/2024/png/5378072/1705731954290-301dc19e-2a67-4e36-9b43-debb436668af.png?x-oss-process=image%2Fwatermark%2Ctype_d3F5LW1pY3JvaGVp%2Csize_40%2Ctext_SmF2YSA4IEd1IFA%3D%2Ccolor_FFFFFF%2Cshadow_50%2Ct_80%2Cg_se%2Cx_10%2Cy_10"></p>
  <p data-lake-id="ub8dd956b" id="ub8dd956b"><br></p>
  <p data-lake-id="ufb27074d" id="ufb27074d"><br></p>
  <h2 data-lake-id="VsC38" id="VsC38"><strong><span data-lake-id="uc222849e" id="uc222849e">双重散列和再哈希的区别</span></strong></h2>
  <p data-lake-id="u36810e8f" id="u36810e8f"><br></p>
  <p data-lake-id="uaf6126e5" id="uaf6126e5"><span data-lake-id="uf2260272" id="uf2260272">通过上面的例子，很多人会疑惑，双重散列和再哈希好像都是多个哈希函数进行的，看上去是一样的？</span></p>
  <p data-lake-id="ub46f5d71" id="ub46f5d71"><span data-lake-id="uced3ff43" id="uced3ff43">​</span><br></p>
  <p data-lake-id="uaa7d9f9c" id="uaa7d9f9c"><span data-lake-id="u2b4f70a6" id="u2b4f70a6">其实大差不差，要说区别的话，在哈希的两个函数没有任何关系，第二次哈希的结果是啥就按照啥进行存储，如</span><code data-lake-id="u1d492bd3" id="u1d492bd3"><span data-lake-id="u0ae39121" id="u0ae39121">key % 7 + key % 10</span></code><span data-lake-id="u4b733102" id="u4b733102"> 的结果是6，那么就直接向6这个位置上存储。而双重散列是开放定址的一种，第二个哈希的结果是在第一次冲突那个位置基础上进行寻址的，如哈希函数是</span><code data-lake-id="u5352b2a8" id="u5352b2a8"><span data-lake-id="u122f9e8f" id="u122f9e8f">3-(key%3)</span></code><span data-lake-id="ub54951ad" id="ub54951ad"> = 2 ，那么最终是在之前的冲突位置向后找2个。</span></p>
  <p data-lake-id="u6e33f0dd" id="u6e33f0dd"><span data-lake-id="u21cd68d1" id="u21cd68d1">​</span><br></p>
 </body>
</html>